00100			     COMPUTER VISION
00200				   by
00300	             Thomas O. Binford, Stanford University    and
00400	             Jay M. Tenenbaum,  Stanford Research Institute
00500	
00600	
00700				Introduction.
00800	
00805	Intelligent computers require knowledge of their environment, and the
00905	most effective means of acquiring such knowledge is by seeing. Vision
01005	will open a new realm of computer applications. Weather analysis from
01105	cloud  maps  and  medical diagnosis from x-rays and blood cell counts
01205	are two of many  high  volume  data  processing  tasks  that  require
01305	pictorial  input.  Man-machine communication will be facilitated if a
01405	person can directly show the computer  a  real  object,  rather  than
01505	having  to  describe  it  symbolically. Designers, for example, could
01605	then easily  obtain  a  computerized  structural  analysis  of  scale
01705	models.
01805	
01905	A  particularly exciting application domain is industrial automation.
02005	Today in industry there are hundreds of  machines  called  industrial
02105	robots.  These  programmable  manipulators can repetitively execute a
02205	precise sequence of motions but have no sensors and are  thus  unable
02305	to   react   dynamically  to  contingencies.  Simple  sensors  and  a
02405	minicomputer  could,  at   slight   additional   cost,   turn   these
02505	manipulators  into  true robots. Primitive visual skills would enable
02605	these machines to align mating parts in assembly operations, increase
02705	reliability  by  self-calibration,  detect flaws and avoid disasters.
02805	Vision will also minimize the present need for precise positioning of
02905	parts  at  each work station; parts could instead be transported in a
03005	bin and picked out as needed.
03105	
03205	The study of perception also provides valuable  insights  into  human
03305	and  machine information processing. Many of the problems encountered
03405	are widespread in intelligence: How is  knowledge  represented?   How
03505	does  it  guide in drawing conclusions from perceptual data? How does
03605	existing knowledge interact with conclusions drawn from an  image  to
03705	acheive  learning?  Issues that arise in the implementation of vision
03805	systems have broad  relevance  to  computer  science:  How  shoulc  a
03905	complex  task  be  partitioned  into  modules? How should the modules
04005	communicate to share their knowledge and  special  capabilities?  How
04105	should  systems  with  highly interdependent modules be structured to
04205	facilitate modification?
04305	
04405	Techniques developed for machine perception cannot be taken literally
04505	as  models  for biological systems because of differences in hardware
04605	and gaps in our  knowledge.   However,  fundamental  limitations  are
04705	shared, suggesting that some of the principles might also be found in
04805	nature. The research may, in turn, occasionally borrow from  biology,
04905	but we cannot copy nature, since again, the details are not yet known
05005	and the hardware is different.
05105	
05205	
05305	Historically,   computer   vision  emerged  from  the  study  of  two
05405	dimensional pattern recognition. However, it is  seldom  possible  to
05505	apply the mathematical formalisms developed for classification to the
05605	analysis of real scenes. Consider  the  visual  requirements  for  an
05705	organism  such  as  a robot. It must manipulate or avoid objects, not
05805	just  classify  them.      Manipulation  requires   three-dimensional
05905	interpretations  and  spatial relations of objects.  In problems like
06005	character recognition, it was attractive to  simply  save  images  or
06105	feature  vectors,  then  match  against an image or part of an image.
06205	But in real scenes, objects occlude one another, they have parts with
06305	joints that move separately, there are many viewpoints, many possible
06405	objects, and many combinations of objects. Object classes,  moreover,
06505	are  often  defined  by  function, not shape (eg. the class of coffee
06605	cups).   Direct template  matching  techniques  are  impractical  for
06705	these requirements, except in very carefully controlled applications.
06805	Perception involves complex deductions  to  understand  an  image  in
06905	terms of a priori knowledge of the world.
07005		ELEMENTS OF A VISUAL SYSTEM
07105	
07205	The computer eye is some form of tv camera with color filters  and  a
07305	turret  or  zoom  lens  for  closeup  views.    The computer controls
07405	filters, lens and other parameters to optimize  the  image  for  each
07505	task  [Tenenbaum].   A recent study has suggested alternative sensors
07605	to overcome  the  inadequate  dynamic  range  of  television  systems
07705	[Binford]. Range information greatly simplifies the interpretation of
07805	scenes. Humans use depth  information  obtained  from  stereo  and  a
07905	variety  of  inferred  cues  such  as motion parallax and the size of
08005	known objects. Since these techniques require subtantial  processing,
08105	it  is  easier  for  machines  to obtain depth by direct measurement.
08205	Several depth sensors based on triangulation have been  built  [Agin,
08305	Shirai, Munson].
08405	
08505	The  image  is  read  into  memory  as  an array of brightness values
08605	(typically 300x300) with 4-8 bits for each sample for each color. The
08705	process  of  interpreting  this  mass  of  numbers  into  a  symbolic
08805	description can  be  thought  of  as  subdivided  into  segmentation,
08905	representation, and interpretation.
09005	
09105	The  process  of  segmentation  partitions  a  scene  into meaningful
09205	entities which may  be  recognizable.     Segmentation  in  character
09305	recognition   is   simple  since  printed  characters  are  spatially
09405	separated and have high contrast with white paper. It  is  harder  to
09505	segment  objects  in  a real scene (even simple scenes) since objects
09605	may overlap  and  will  not  usually  be  separable  from  the  local
09705	background  by  a single attribute like brightness contrast. Instead,
09805	segmentation must proceed by seeking regions of  uniform  brightness,
09905	color,  or  texture  (itself  a  complex descriptor), or regions with
10005	regular boundaries. Segmentation may also depend  on  inferred  depth
10105	cues (e.g., texture gradients or suspected occlusion).
10205	
10305	In  what  form  can  we represent objects internally in the computer?
10405	The simplest form is a pictorial template,  an  array  of  brightness
10505	values  to  be  matched  directly  against  fragments  of  scenes  by
10605	correlation. Given the inadequacies of this representation,  we  must
10705	describe  partitioned  regions  symbolically  in  terms  of extracted
10805	features like color, size, texture, and shape.  All these  properties
10905	are inferred by complex processes from the image.  Simple descriptors
11005	for shape or texture may be used in simple tasks and limited context.
11105	Shape might be described by the ratio of the squared perimeter to the
11205	area of a region.  More sophisticated shape  representations,  needed
11305	for a wider range of tasks, are described later.
11405	
11505	Interpretation  is  often  expressed  as computing a distance measure
11605	between an object and a stored model.  For simple cases that  can  be
11705	useful.    When  objects are occluded, there must be a partial match.
11805	When objects are not identical, judgments  of  similarity  depend  on
11905	representation  of  shape and representation of the task, in order to
12005	define important differences.  The most useful approach is  to  build
12105	up   symbolic   descriptions   and   make  symbolic  descriptions  of
12205	differences.   Sometimes, there are few enough models  that  matching
12305	with  each  model  is possible. More generally, the observed features
12405	must first be used to retrieve likely  models  from  a  large  visual
12505	memory.
12605	
12705	The integration of segmentation, representation and interpretation to
12805	acheive perception is illustrated by a system built at the University
12905	of  Edinburgh  [Barrow]  which  can recognize a small set of ordinary
13005	objects  such  as  pencils,  eye-glasses  and  teacups.  Objects  are
13105	presented  against a contrasting background. Segmentation is acheived
13205	by partitioning the scene into regions of uniform brightness. Objects
13305	are  represented  by  relational  graphs  detailing  gross attributes
13405	(size, shape) of their  principle  regions  and  spatial  constraints
13505	between   them.   Interpretation   is  accomplished  by  mapping  the
13605	relational graph descriptions of known  objects  onto  the  segmented
13705	regions obtained from the scene and seeking the best match.
13805	
13905	Experience  with  early  bottom-up  systems  of  this type led to the
14005	realization that the three basic processes  of  a  perceptual  system
14105	were  highly  interdependent; one cannot proceed sequentially through
14205	segmentation, representation and interpretation and expect to  obtain
14305	a globally consistent interpretation for all objects in a scene.  One
14405	problem is that no reliable  basis  exists  for  judging  the  global
14505	significance   of  segmentation  boundaries  using  local  similarity
14605	criteria. Segmentation must be guided  by  interpretation  to  choose
14705	among  many alternative partitionings, that which leads to a globally
14805	consistent and reasonable description of the scene.
14905			BLOCKS WORLD
15005	
15105	To  avoid some of these difficulties, research concentrated initially
15205	on scenes of toy blocks.  Roberts' important work  opened  the  field
15305	[].  Objects were represented as built up of three primitive parts, a
15405	block, a wedge, and a hexagonal prism. The program assumed  it  would
15505	first  obtain  perfect  line drawings. Interpretation meant finding a
15605	three-dimensional model which after translation, rotation and scaling
15705	could  be projected to match part of the image.  The recognized piece
15805	was then cut away and  the  remainder  considered.   Primitives  were
15905	represented  by  their  vertices in three dimensions.    To decide on
16005	likely image points which belonged to  a  single  body,  the  program
16105	attempted  to  identify  unobscured  polygons,  then  match  sets  of
16205	vertices to topologically similar model vertices. Line drawings  were
16305	formed by a sequence of local operations.  Candidate edge points were
16405	considered by thresholding the gradient of intensity.  Isolated  edge
16505	points  were  discarded.   Connected line fragments were concatenated
16605	into lines which were segmented at  corners  by  a  sequential  least
16705	squares line fit.  Merging of colinear lines bridged some gaps.
16805	
16905	That  system  organization has proven inadequate. It is not enough to
17005	use models and template matching. Producing perfect line drawings  is
17105	not  practical:   some  lines  are  missed;  shadows, reflections and
17205	surface markings cause extra lines; errors  made  at  one  stage  are
17305	compounded  by later stages.  These deficiencies motivated subsequent
17405	research.
17505	
17605	Guzman [] found it possible to segment complex  scenes  into  objects
17705	without template matching, by observing that some vertices give local
17805	evidence that adjacent regions belong to the same body. In figure  1,
17905	vertices  A,B,C,E,G  and H give evidence that adjacent regions belong
18005	to the same body, while vertex F does not.  Vertex D which  resembles
18105	G gives misleading evidence.  To avoid such coincidences, the program
18205	required confirmation.      Regions linked  twice  were  joined  into
18305	clusters;  regions  linked  twice  to  a  cluster  were  also joined.
18405	Regions linked only to a single cluster  were  also  joined  to  that
18505	cluster.  Eventually,  the  program  evolved  to  include inhibitions
18605	against certain links by requiring similar conditions at both ends of
18705	a line.   Other links were introduced without much motivation.
18805	
18905	This  program  was an important advance.    Bodies could be segmented
19005	without recognition and without explicit  models.   The  program  did
19105	surprisingly   well,   but   had   problems   with  holes  and  other
19205	non-convexities,  and  with  accidental  alignment.  being  told  the
19305	background.  Guzman  also  could  not  cope  well with imperfect line
19405	drawings. His program would fail of figure 2 because a  missing  line
19505	makes region R3 common to both the block and wedge. Falk [ ] was able
19605	to avoid some of the errors associated  with  missing  boundaries  by
19705	using  a  Guzman like approach to link line segments likely to belong
19805	to the same object instead of regions.
19905	
20005	The limited generality of both these programs was  due  to  the  fact
20105	that  they  were  implemented as a collection of adhoc heuristics for
20205	segmentation with no explicit understanding of line  drawings.  Thus,
20305	while Falk himself realized that regions like R3 could not arise in a
20405	scene containing only trihedral solids, his program could not  reason
20505	at  this level. Huffman [] and Clowes [] made theoretical analyses of
20605	objects with only trihedral vertices (three planes at  each  vertex).
20705	By  classifying  edges  as  convex, concave and obscuring, they could
20805	require consistent labels for a drawing, and reject some drawings  as
20905	impossible  objects  under their conditions.   Waltz [] expanded that
21005	labelling of lines to include cracks  and  whether  adjacent  regions
21105	were  shadowed  or illuminated. Each vertex had many interpretations.
21205	It would seem that such large  numbers  of  possible  interpretations
21305	would   be  unmanageable.     instead,  the  increased  precision  of
21405	descriptions allows rapid discarding of wrong interpretations.    Not
21505	only  are solutions possible, they are quickly obtained. Instead of a
21605	complete tree  search,  it  was  adequate  to  consider  vertices  in
21705	sequence, eliminating inconsistent interpretations as each new vertex
21805	was added.  This produced all possible interpretations  of  a  scene.
21905	However,   some   evaluations  were  possible  to  choose  reasonable
22005	interpretations, in cases with ambiguous interpretations. A  detailed
22105	survey  of  the work through Huffman appears in a recent text by Duda
22205	and Hart [1973].
22305	
22405	
22505	
22605	
22705	
22805	The best performance in  extracting  line  drawings  from  television
22905	images of polyhedra is given by the Shirai [] and the Binford-Horn []
23005	line finders.  Shirai's system performs better,  but  requires  large
23105	contrast  between  objects and background (e.g., white on black), and
23205	finds only features and objects for which  cues  are  available  from
23305	context.    The  Binford-Horn  system is able to find most lines in a
23405	scene of white blocks on a white background  in  arbitrary  lighting.
23505	It  misses  a few lines which can usually be inferred from those that
23605	were found, and garbles some vertices.    The two  are  complementary
23705	and should be combined.
23805	
23905	The two programs are based on different principles.  Shirai's program
24005	began with only outer boundaries, and  tried  to  guess  as  much  as
24105	possible  at  each  stage.     At vertices, the extension of boundary
24205	lines was tested.  Completions for unterminated lines  were  searched
24305	for.     Additional lines were tested for at vertices, including some
24405	parallel to lines at adjacent vertices.  The use of context  involved
24505	not changing thresholds, but using special-purpose operators:  verify
24605	a line at known position and angle; find a line through a vertex. The
24705	Binford-Horn  system  was  intended  to provide the base for a system
24805	such as Shirai's by providing a partial line drawing without  special
24905	background.  It used a local directional edge operator and an optimal
25005	curve sequential decision process to extend curves and test  at  each
25105	extension,  whether  to  keep, terminate, or extend further. Figure 3
25205	illustrates the complexity of scenes handled by Shirai's program.
25305	
25405	It is interesting  to  compare  these  systems  with  the  biological
25505	system.    Directional  edge  operators  are  scanned  over the image
25605	[Binford, Hueckel];  these  compare  with  the  edge  detector  cells
25705	discovered  by Heubel and Wiesel[] in higher animals.    In practice,
25805	large gradients at reflections and curved surfaces  cause  masses  of
25905	spurious  edge  fragments.   These were eliminated by subtracting the
26005	local average at each point, thus subtracting  out  smooth  gradients
26105	[Binford].   This  process  is  familiar as lateral inhibition in the
26205	retina of animals.
26305	
26405	
26505	
26605			REAL WORLD VISION
26705	
26805	
26905	
27005	The  blocks  world  illustrates  many  basic   aspects   of   machine
27105	perception,   but   many   other  critical  problems  encountered  in
27205	perceiving real world scenes do not arise.    Important  problems  in
27305	segmentation   were   avoided  by  using  uniformly  painted  blocks.
27405	Segmentation of boundaries was specialized  to  straight  lines.  The
27505	region-growing  and edge-finding techniques developed in this context
27605	cannot cope with the  textures  and  variations  of  brightness  that
27705	predominate in the real world.
27805	
27905	The  elaborate  topological  descriptions  that  characterized simple
28005	polyhedra are inappropriate  or  unobtainable  for  most  real  world
28105	objects.  In some cases we must rely only on gross characteristics of
28205	shape, texture and other features, e.g., to  distinguish  trees  from
28305	mountains.  In other cases, we require more complex descriptions than
28405	characterized polyhedra, as in  descriptions  of  machined  parts  or
28505	people.
28605	
28705	It  is  not  conceivable  in  real  world  scenes to search through a
28805	complete set of known prototypes seeking interpretations.  The system
28905	must  limit interpretations to those familiar in the context, and use
29005	brief descriptions to  select  a  small  subset  of  possible  object
29105	interpretations.   Segmentation  can  then  attempt  to  find uniform
29205	regions for attributes which best characterize these objects.
29305	
29405	The key problem faced in real world vision is  information  overload,
29505	and  it must be faced, as above, by tightly coordinating segmentation
29605	and interpretation with world knowledge. The overload is  not  to  be
29705	solved  by  merely  building  faster  computers  and bigger memories;
29805	hardware improvements will aid adequate techniques but do little  for
29905	exhaustive techniques.
30005	
30105	Description  of  simple  polyhedral scenes was difficult enough; with
30205	these added obstacles, is there hope for success  in  perceiving  the
30305	real  world?   We think so!  Although it may not be possible (or even
30405	meaningful) to obtain exhaustive descriptions of  real  scenes,  such
30505	descriptions  are  seldom  needed; a system will usually be concerned
30605	with only a few objects objects required to complete a specific task.
30705	For  blocks, we restricted our programs to black and white images and
30805	distinguished structures of blocks solely on the basis of shape.   In
30905	the  real  world, there is a tremendous redundancy of visual cues. We
31005	can use color, texture, depth, size (which is not very  relevant  for
31105	blocks),  and  surface  orientation, as well as shape.  Finally, real
31205	world objects are usually  found  in  well  defined  contexts;  e.g.,
31305	telephones   are  expected  on  tables  but  not  in  waste  baskets.
31405	Recognition of a few promminent landmarks,  combined  with  a  priori
31505	knowledge  of the environment can thus severely restrict what objects
31605	may be present in each part of the scene. While these objects may  be
31705	difficult   to  describe,  there  will  usually  be  sufficient  cues
31805	available to discriminate easily amongst the alternatives. Real world
31905	vision  can  be  viewed  as  a strategy problem: Given a task, decide
32005	where to look for objects of interest and  then  how  to  distinguish
32105	them from others that might also be present.
32205	
32305	The  principle  work to date on real world vision has concentrated on
32405	segmentation and representation. Studies for agricultural  and  earth
32505	resources  surveys  have  considered  texture  as  a  two-dimensional
32605	problem.  Bajcsy [] has analyzed outdoor scenes for which perspective
32705	and  three-dimensional  description are important.      Textures were
32805	described hierarchically in terms of  simpler  texture  elements  and
32905	their  spatial  relationships.   Descriptors for texture elements and
33005	relations were derived from  Fourier  analysis.   Typical  attributes
33105	were  directionality (if any), size, contrast, and spacing of texture
33205	elements.    The Fourier transform was found troublesome,however, and
33305	color  descriptors  were  added  to  improve performance.  Some depth
33405	relations could be observed from texture gradient.   An  attempt  was
33505	made  to obtain consistent interpretations by first confirming region
33605	boundaries  by  independent  properties,   making   three-dimensional
33705	interpretations,  and  matching region descriptors with those of sky,
33805	trees, grass, etc.  in a world model.
33905	
34005	The  quality  of  interpretation  was  limited  by  unreliability  of
34105	region-growing  processes. Further work in outdoor scenes attempts to
34205	incorporate the  world  model  and  interpretation  into  the  region
34305	growing process. Regions are merged not only because of similarity of
34405	properties, but because the consistency of semantic interpretation is
34505	improved.
34605	
34705	
34805	Typical  robot  tasks  such  as  manipulation,  collision  avoidance,
34905	display  and  recognition  were  analyzed  to determine computational
35005	primitives required for descriptions of shape.  Although  some  would
35105	disagree, the general criteria for shape representation are [ ]:
35205	
35305	a)  Representations  should  be  symbolic at a high level in order to
35405	interface with knowledge of the problem  domain.  b)  Representations
35505	should  depend  on  segmentation into parts, which may have subparts.
35605	Primitives should allow a natural  choice  of  parts.  c)  Primitives
35705	should  be three-dimensional volume descriptions, rather than surface
35805	descriptions.  d)  Descriptions  should  be  generative.   A   modest
35905	collection  of  primitives  should allow description of a vast set of
36005	objects.
36105	
36205	We will outline one representation that fulfils these desiderata  for
36305	a  large  class  of curved objects. Objects are described in terms of
36405	components which are simple to describe,  and  the  relationships  of
36505	these  parts.  A useful shape primitive for many curved objects is an
36605	arbitrary space curve, and  normal  cross-sections  along  this  axis
36705	(figure  5).    Snake-like  objects,  helices,  toroids,  and locally
36805	helical and toroidal shapes are naturally described [Binford 71]. Our
36905	basic criteria for accepting a piece as simple are that the direction
37005	of the axis be continuous and that the cross-section  function  along
37105	the  axis  be continuous.  We look for portions with large changes in
37205	the cross- section, and consider them as likely places for segmenting
37305	the  object.   The  segmentation process must be flexible and able to
37405	generate  alternate  propositions.   A  higher  level  routine   will
37505	ultimately   select   from  the  alternatives.   Figure  6  shows  an
37605	experimentally obtained computer description of a doll [Agin 72].
37705			INDUSTRIAL APPLICATIONS
37805	
37905	Recently,  several  laboratories  have begun to apply techniques from
38005	perception research to practical  industrial  tasks.  General  Motors
38105	laboratories  has  succeeded in mounting a wheel on an axle. Stanford
38205	Research Institute and Hitachi Ltd. have  each  demonstrated  systems
38305	which can distinguish sheet metal parts on a moving conveyor belt and
38405	determine their orientation to enable manipulation. Template matching
38505	techniques  were used to take advantage of the two dimensional nature
38605	of these tasks. Moreover, the conveyor demonstrations relied  on  the
38705	contrast  between  shiny metalic parts and the black belt to simplify
38805	segmentation. Many industrial processes share similar constraints  or
38905	can be readily redesigned to do so. We thus expect a proliferation of
39005	industrial applications of computer perception in the near future.